/*
 * 4.6
 * Design an algorithm and write code to find the first common ancestor of two nodes
 * in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not
 * necessarily a binary search tree.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
using namespace std;

typedef struct _tree_t {
    int value;
    struct _tree_t *left;
    struct _tree_t *right;
} tree_t;

/* XXX: Reference was not passed. */
/* XXX: This function does not add the root node to result. */
bool find_route_old(tree_t *root, tree_t *node, stack<tree_t *> &result)
{
    if (root == node) {
        return true;
    }
    bool find = false;
    if (root->left) {
        if (find_route_old(root->left, node, result)) {
            result.push(root->left);
            return true;
        }
    }
    if (root->right) {
        if (find_route_old(root->right, node, result)) {
            result.push(root->right);
            return true;
        }
    }
    return false;
}

bool find_route(tree_t *root, tree_t *node, stack<tree_t *> &result)
{
    if (root == node) {
        result.push(root);
        return true;
    }
    bool find = false;
    if (root->left) {
        if (find_route(root->left, node, result)) {
            find = true;
        }
    }
    if (!find && root->right) {
        if (find_route(root->right, node, result)) {
            find = true;
        }
    }
    if (find) {
        result.push(root);
    }
    return find;
}

tree_t *find_common_ancestor(tree_t *root, tree_t *node1, tree_t *node2)
{
    stack<tree_t *> s1, s2;
    bool b1 = find_route(root, node1, s1);
    bool b2 = find_route(root, node2, s2);
    tree_t *last_equal = NULL;
    if (b1 && b2) {
        while (!s1.empty() && !s2.empty() && s1.top() == s2.top()) { // XXX: Empty was not checked.
            last_equal = s1.top();
            s1.pop();
            s2.pop();
        }
    }
    return last_equal;
}

tree_t *new_tree(int v)
{
    tree_t *t = (tree_t *)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    t->value = v;
    return t;
}

void free_tree(tree_t *root)
{
    if (!root) {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main()
{
    tree_t *nodes[7];
    for (int i = 0; i < 7; i++) {
        nodes[i] = new_tree(i);
    }
    tree_t *root = nodes[0];
    root->left = nodes[1];
    root->right = nodes[2];
    nodes[1]->left = nodes[3];
    nodes[1]->right = nodes[4];
    nodes[4]->left = nodes[5];
    nodes[4]->right = nodes[6];
    tree_t *t = find_common_ancestor(root, nodes[5], nodes[6]);
    printf("common ancestor of 5 and 6 is: %d\n", t ? t->value : -1);
    t = find_common_ancestor(root, nodes[2], nodes[3]);
    printf("common ancestor of 2 and 3 is: %d\n", t ? t->value : -1);
    free_tree(root);
    return 0;
}
